Sorting Algorithms

About Sorting

$$ \begin{aligned} A_n &= \{a_k\} \\ &\downarrow \\ A'_n &= \{a_k': \forall i < j, a'_i < a'_j \} \end{aligned} $$

Insertion Sort

Incremental Insert.

Code

∀ i ∈ [1, |A|], j = i:
    while (j > 0) ∧ (A[j] < A[j-1]):
        A[j] ⇋ A[j-1]
        j ⇋ j-1

Asymptotic

$$ T(N) = \mathcal{O}(N^2) $$

Selection Sort

Select the least to insert.

Math

$$ a'_{j+1} = \arg\max_{a_i \in A_{n}\backslash\{a_k\}_{k=1}^{j}} a_i $$

Code

∀ i ∈ [1, |A|]:
    δ = argmin A[i:]
    A[i] ⇋ A[δ]

Asymptotic

$$ T(N) = \mathcal{O}(N^2) $$

by Jon